Operating systems that use single tasking have existed on host data processing systems for many years. In such systems, the operating system executes computer programs, subroutines or tasks serially. Before beginning a new task, the previous one must be completed. The waiting delay may last for a certain period and the throughput of the operating system may be impacted. Thus, the system may break down.
This problem has led to the advent of the multitasking or multi thread operating systems in which each computer program or task is divided into a plurality of tasks or streams of execution. Furthermore, multitasking operating systems have also been extended to multiprocessor environments where tasks of the same or different programs can be executed in parallel on different computer processors. While such multitasking operating systems optimize the use of one or more processors, they do not permit the application program developer to adequately influence the scheduling of the task executions.
There are different mechanisms for processing the set of queues in which the tasks are queued. Such mechanisms are based on three main basic principles:
the principle based on priority: wherein a set of priorities is assigned to the different queues and the queue with highest priority is served as long as it is not empty. In such case, the queues with lower priorities might never be served because of the important traffic on higher priority queues; PA1 the principle based on a predefined processing sequence: wherein an order for processing of queues is defined according to a priority that is defined by repetition of a queue in the sequence. Whatever the status of the queues are, the sequence is executed (high priority is defined by a high number of occurrences of a given queue in the sequence); and PA1 the principle based on time: wherein each queue is assigned a processing time. The queue is to be processed when the corresponding processing time has elapsed. In this case, the queue priority is defined according to the value of the corresponding processing time (the higher the priority of the queue is, the lower the relevant processing time should be). PA1 (a) dequeueing, in normal state, successively queued messages from a plurality of queues (MIQ) according to their queue priorities; PA1 (b) interrupting this normal state to enter a critical state, by dequeueing successively queued messages from a plurality of critical queues (MIQ) according to their queue priorities, the critical queues having aging times that exceed predetermined values (Delay.Maxi); and PA1 (c) returning to the previous normal state with its set of parameters to continue until the next critical state occurs or until the end of the scheduling cycle. PA1 a first register for static weight (Stat.Ni) corresponding to the number of messages which may be pulled out from the queue, the first register being implemented in connection with a second register for current weight (Cur.Ni) corresponding to the number of messages left that are allowed to be dequeued from the queue, for processing queued messages in normal state; and PA1 a third register for maximum delay (Delay.Maxi) corresponding to the maximum waiting time of a non-empty MIQ to be dequeued, the third register being implemented in connection with a fourth register for dormant time (Dorm.i) corresponding to the elapsed time since the MIQ was last served, for processing queued messages in critical state when the fourth register exceeds the third register.
In any one of these mechanisms which are to some extent static, the queue evolution and aging are not taken into consideration. In order to cope with the data traffic and not to impact on the throughput of the queue processing, it is required to implement a mechanism that is based on criteria which may have static requirements but which may also evolve in real time so as to process within acceptable delays all the messages in the queues, even the ones with the lowest priorities.
In U.S. Pat. No. 5,630,128, a controlled scheduling of program threads in a multitasking operating system is disclosed. In this technique, a multitasking operating system permits application programs to influence a schedule of execution of programs to which are assigned priority levels and dispatch classes in which the threads reside. According to these parameters, the operating system queues the highest priority thread which is available for execution from each dispatch class onto a run list for execution by a processor. The highest priority thread on the run list is executed first. But in this kind of implementation, there is no guarantee that the lowest priority thread can be processed within an acceptable delay unless no higher priority thread remains on the run list.
In another U.S. Pat. No. 5,437,032, a task scheduler for a multiprocessor system, each containing one or more processors, concurrently execute tasks into which jobs as database queries are divided. Each job is assigned a weight in accordance with the external priority of the job. A desired level of concurrent task activity is defined for each of the jobs. The actual level of concurrent task activity for each of the jobs is also determined. The jobs are prioritized for execution of awaiting tasks in accordance with the discrepancy between the desired level of concurrent task activity and the actual level of concurrent task activity for each of the jobs. This technique is based on the definitions of desired and actual levels and does take into account the time constraint wherein a task or a set of tasks are to be executed within a certain delay.
In U.S. Pat. No. 5,247,671, scalable schedules for a serial communications controller in a data processing system is disclosed. In this document, the tasks are scheduled at different priority level so that time-critical tasks are performed quickly enough to prevent data loss. The notion of time-critical in this patent came directly from the notion of priority. Both notions are not independent, meaning that the tasks are arranged according to certain priority and in this arrangement, some or all the tasks might have time-critical values.